// 一维数组前缀和
class NumArray {
  constructor(nums) {
    const preSum = new Array(nums.length + 1)
    preSum[0] = 0
    for (let i = 1; i < preSum.length; i++) {
      preSum[i] = preSum[i - 1] + nums[i - 1]
    }
    this.preSum = preSum
  }
  sumRange(left, right) {
    return this.preSum[right + 1] - this.preSum[left]
  }
}

// 二维矩阵前缀和
class NumMatrix {
  constructor(matrix) {
    const m = matrix.length, n = matrix[0].length
    const preSum = new Array(m + 1).fill(null).map(() => new Array(n + 1).fill(0))
    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        preSum[i][j] = matrix[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1]
      }
    }
    this.preSum = preSum
  }
  sumRegion(row1, col1, row2, col2) {
    return this.preSum[row2 + 1][col2 + 1] - this.preSum[row2 + 1][col1] - this.preSum[row1][col2 + 1] + this.preSum[row1][col1]
  }
}
